1. Field of the Invention
The present invention relates to image processing, and, in particular, to half-pel motion estimation used in video coding.
2. Description of the Related Art
In video coding, it is known to encode images using motion-compensated inter-frame differencing in which blocks of image data are encoded based on the pel-to-pel differences between each block in an image currently being encoded and a selected block in a reference image. The process of selecting a block in the reference image for a particular block in the current image is called motion estimation. The goal of motion estimation is to find a block in the reference image that closely matches the block in the current image so that the pel-to-pel differences between those two blocks are small, thereby enabling the block in the current image to be encoded in the resulting compressed bitstream using a relatively small number of bits.
In a typical motion estimation algorithm, a block in the current image is compared with different blocks of the same size and shape in a defined search region in the reference image. The search region is typically defined based on the corresponding location of the block in the current image with allowance for inter-frame motion by a specified number of pels (e.g., 8) in each direction. Each comparison involves the computation of a mathematical distortion measure that quantifies the differences between the two blocks of image data. One typical distortion measure is the sum of absolute differences (SAD) which corresponds to the sum of the absolute values of the corresponding pel-to-pel differences between the two blocks, although other distortion measures are also used.
There are a number of methods for identifying the block of reference image data that "best" matches the block of current image data. In a "brute force" exhaustive approach, each possible comparison over the search region is performed and the best match is identified based on the lowest distortion value. In order to reduce the computational load, alternative schemes, such as log-based or layered schemes, are often implemented in which only a subset of the possible comparisons are performed. In either case, the result is the selection of a block of reference image data as the block that "best" matches the block of current image data. This selected block of reference image data is referred to as the "best integer-pel location," because the distance between that block and the corresponding location of the block of current image data may be represented by a motion vector having X (horizontal) and Y (vertical) components that are both integers representing displacements in integer numbers of pels. The process of selecting the best integer-pel location is referred to as full-pel or integer-pel motion estimation.
In order to improve the overall encoding scheme even further, half-pel motion estimation may be performed. In half-pel motion estimation, after performing integer-pel motion estimation to select the best integer-pel location, the block of current image data is compared to reference image data corresponding to different half-pel locations surrounding the best integer-pel location.
FIG. 1 shows a graphical representation of the locations of the relevant blocks of reference image data for half-pel motion estimation. In FIG. 1, location 0 (*) corresponds to the best integer-pel location, locations 1-8 (o) correspond to the 8 integer-pel locations immediately surrounding the best integer-pel location, and locations 1'-8' correspond to the 8 half-pel locations immediately surrounding the best integer-pel location.
In a typical half-pel motion estimation algorithm, after the best integer-pel location is selected (using an appropriate integer-pel motion estimation algorithm), each of the 8 different half-pel locations 1'-8' is compared with the block of current image data (i.e., 8 distortion values are generated) to determine which if any of the 8 half-pel locations provides a better match (e.g., lower distortion value) with the block of current image data than the best integer-pel location. The best of these 9 locations is then used for motion-compensated inter-frame differencing.
For each half-pel comparison, data corresponding to two or more different integer-pel blocks in the reference image are interpolated before computing the distortion value. For example, for the half-pel comparison at location 1', the reference image data corresponding to the integer-pel location 0 is linearly interpolated with the reference image data corresponding to the integer-pel location 1 to generate interpolated reference image data that is then compared with the block of current image data to generate a distortion value for location 1'. For the half-pel comparison at location 2', the interpolated reference image data are generated by performing two-dimensional linear interpolation using the reference image data corresponding to four integer-pel locations 0, 1, 2, and 3. As can be appreciated, the computational load involved in generating the interpolated reference data and then generating the distortion value for each comparison in such half-pel motion estimation can be quite large.